​ 百万富翁问题是姚期智先生在1982年提出的第一个安全双方计算问题,两个百万富翁街头邂逅，他们都想炫一下富，比比谁更有钱，但是出于隐私，都不想让对方知道自己到底拥有多少财富，所以要在不借助第三方的情况下，知道他们之间谁更有钱。

①这里假设Alice和Bob就是这两个百万富翁，Alice拥有财富i百万，Bob拥有财富j百万，假设他们两的财富都没有超过N百万，即1 ≤ i , j ≤ N，如下图所示：

②Alice随机选择一个大随机数x，用Bob的公钥加密后得到x的密文c，如下图所示：

③Alice将c-i发送给Bob（减去i是为了破坏密文c），如下图所示：

④Bob首先计算N个数：yu=DSKB(c-i+u)， 其中u=1,2…N（这里加上u是为了能在yu的数列里面还原出被破坏的密文），然后随机选择一个大素数p，再计算N个数：zu=yu mod p, 其中u=1,2…N，如下图所示：

⑤接着Bob对于所有的0≤a≠b≤N，是否都满足|za-zb|≥2（如果小于2的话，就可能导致第⑥步里面的数串,zj+1+1,zj+2+1,…,zN+1和zj+1相等），若不满足，则重新选择大素数p并重新验证。如下图所示：

⑥如果满足，Bob将以下的N个数串和p：(z1，z2,…,zj,zj+1+1,zj+2+1,…,zN+1,p)一起发给Alice（这里从zj+1开始每一项+1是为了在第⑦步Alice验证的时候能得出正确的结论，而且也保护了Bob的隐私，不能泄露j的值），如下图所示：

⑦假设Alice收到这N+1个数的第i个数满足Zi=x(mod p)，则结论是i≤j，否则i＞j（对应第④步中的zu=yu mod p）。如下图所示：

这部分的算法思想参考了csdn上面Bertramoon的博客，只不过这里换成java实现。

公钥为( n , e )，私钥为( n , d )；